3ia is the only theory of phylogenetics that does not rely on a “matrix” (i.e. table) representation of characters/taxa (taxa/areas in biogeography), and does not need outgroup taxa (or areas). LisBeth implements for the first time representation of characters as hierarchies or rooted trees of states (Cao et al., 2007) and assigns character states as synapomorphies of taxa.

Characters, i.e. rooted character state trees entered by users, are reduced to sets of three-item statements (3is hereafter). Each 3is represents the minimal hierarchical statement, i.e. given three entities (e.g. terminal taxa or areas of endemism), two of them are more closely related to each other than any is to the third. Thus, all 3is have the same minimal hierarchical structure (A (B C)). Fractional weighting (FW) is applied to 3is as described by Nelson and Ladiges (1992).

Hennig (1966), the German entomologist who founded cladistic analysis, defined congruence as the criterion of optimality in cladistic analysis. To discover congruence one might use either parsimony (e.g. Farris, 1983) or compatibility analyses (e.g. Estabrook et al., 1976). It has been shown (Wilkinson, 1994a) that both criteria are computationally identical in 3ia. However, compatibility allows further theoretical implementations; hence, LisBeth uses compatibility. Relationships among taxa or biogeographic areas are found by combining the 3is deduced from all characters. So far, 3ia only benefits from exact algorithms, i.e. exhaustive and branch and bound (Hendy and Penny, 1982) searches, which are applied on 3is, associated with their FW. Thus, LisBeth first measures the sum of FW of compatible 3is. Optimal trees have the maximum amount of compatible 3is, i.e. are built from the max-clique of mutually compatible 3is that has the biggest sum of fractional weights.

We wanted the software to be modular; hence, LisBeth is currently a package of several programs, mainly written in C language for improved performance, including parallel computation when needed. There are command-line utilities, which can be combined to produce the desired sequence of computation. For instance, scripts can be written quickly with shell interface, while sophisticated computation can be run by confirmed programmers using modules of the popular Python language (www.python.org). Thus, LisBeth is aimed to become an open platform for computing in 3ia. LisBeth also includes a Graphical User Interface (GUI) (Fig. 1).

Characters are edited via the GUI as rooted trees (Fig. 1A) or Venn diagrams (Fig. 1B). The classes (or nodes) of a character are first created and then filled with taxa (Fig. 1C) according to the state they present. Names of character states are shown in Fig. 1D. The list of characters appears in Fig. 1E.

Displayed trees may be edited manually (with parenthetical notations or Venn diagrams via the GUI), i.e. relative positions of terminals may be modified, and/or saved in eps format for printing. LisBeth automatically arranges trees in four different ways and terminal taxa may be automatically aligned.

LisBeth implements exact algorithms (exhaustive and branch and bound searches, Fig. 1F).

The procedure may be separated in two steps: 1) rearrangement of characters in 3is associated with their FW; 2) search for the optimal trees. The list of optimal trees is displayed in Fig. 1G.

LisBeth calculates and displays the results (i.e. most compatible trees) in a list of numbered trees from “[1]” to “[n]”, and recombines the intersection tree, labelled “[0]” (Figure 1G). The intersection tree is a summary, more than a consensus, a tree built from, and only from, the 3is that are common to all the optimal trees and characters (Cao et al., 2009). It summarizes all the information that is common to the optimal trees, and only this information. The intersection tree has the desirable characteristics of consensus trees (Wilkinson, 1994b). Furthermore, it takes into account the information present in the characters that served to build the optimal trees, whereas this information is lost in consensus trees.

LisBeth implements the 3ia method for character interpretation, based on the tree topology and character state distributions. For each node, synapomorphies are shown in green and homoplasies in red (Fig. 1H). Orange colour means that both synapomorphies and homoplasies are found for a given node. The character interpretation can be displayed for each character independently as well as for a set of selected characters (here, characters indicated by the red colour in Fig. 1E) or for a given node. Relative position of the lists of character states (displayed in boxes with a colourful banner) can be modified since each box is linked with the corresponding node.

In 3ia the retention index (Archie, 1989 and Farris, 1989) measures the proportion of 3is deduced from the primary hypotheses of homology that fit the optimal tree (Kitching et al., 1998). The retention index value of optimal trees and of the intersection tree are automatically generated and displayed, as well as the per-character values (Fig. 1H). We define a new completeness index (Compl), representing the proportion of 3is deduced from the intersection tree that are also present in the characters, and it can be displayed as well (Fig. 1H). Let A be the number of 3is common to all optimal trees found (i.e. used to rebuild the intersection tree); let B be the number of 3is deduced from the rebuilt intersection tree. Compl = A B \[ \text{Compl}=\frac{A}{B} \]

Compl can be seen as a measurement of the degree of support provided by primary hypotheses of homology. A low value implies that a significant proportion of 3is deduced from the intersection tree are not present in the character set likely because few characters support the cladogram.

LisBeth is also an appropriate tool for cladistic biogeography (Nelson and Ladiges, 1991). Users supply a list of taxa and areas, the area(s) of endemism where each taxon lives and the cladograms of taxa that provide the evidence of area relationships. LisBeth translates cladograms of taxa to taxon-area cladograms (TACs) by replacing terminal taxa with the areas of endemism where representatives are found. This may lead to two well-known problems: redundant areas (due to taxic paralogy, i.e. taxon diversification prior to area duplication) and widespread taxa (or Multiple Areas in Single Terminals [MASTs] according to Ebach et al., 2005). LisBeth applies the Paralogy-free Subtree analysis (Nelson and Ladiges, 1996) and the Transparent method (Ebach et al., 2005), respectively, to resolve them. Redundancy of areas implies conflicting relationships; the Paralogy-free Subtree analysis combines subsets of non-conflicting 3is within TACs into subtrees. The Transparent method is the first method that supplies a separate procedure dealing with MASTs, which uses the Paralogy-free Subtree analysis rather than solving paralogy. It provides all biogeographic 3is implied by widespread taxa of the TACs.

LisBeth offers the possibility to extend each taxonomist's daily work. Whenever a knowledge base is created, i.e. a set of structured descriptive data, it is possible to define a set of characters from an Xper² (Ung et al., 2010) knowledge base. For the sake of interoperability, a particular, very simple, scripting format allows choosing among descriptors, specifying hypotheses of homology to any set of descriptor-states, and accepting, discarding, or creating new dependencies among characters.

LisBeth may also export 3is matrices in NEXUS format for MP searches. It is capable of importing the results for empirical comparisons under different cladistic interpretations.